package 单调栈_上;

// 子数组的最小值之和
// 给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
// 由于答案可能很大，答案对 1000000007 取模
// 测试链接 : https://leetcode.cn/problems/sum-of-subarray-minimums/

public class Code03_SumOfSubarrayMinimums {

    public static int MOD = 1000000007;

    public static int MAXN = 30001;

    public static int[] stack = new int[MAXN];

    public static int r;

    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        r = 0;
        long ans = 0;
        // 注意课上讲的相等情况的修正
        // i ---> arr[i]
        // 计算公式：从 left ~ i 范围内，[left+1 ~ i-1]的最小值：arr[cur]
        // (cur - left) * (i - cur) * arr[cur]
        for(int i = 0, cur; i < n; i++){
            while (r > 0 && arr[stack[r-1]] >= arr[i]){
                // 栈弹出
                cur = stack[--r];
                // 如果栈空了，则左边最近最小的值在 -1 位置
                int left = r == 0 ? -1 : stack[r-1];
                ans = (ans + (long) (cur - left) * (i - cur) * arr[cur]) % MOD;
            }
            stack[r++] = i;
        }

        // 清算阶段，栈中剩余的数，这些数字都没有 右边最近最小的数字，则认为其在越界位置：n
        while (r > 0){
            int cur = stack[--r];
            int left = r == 0 ? -1 : stack[r-1];
            ans = (ans + (long) (cur - left) * (n - cur) * arr[cur]) % MOD;
        }
        return (int) ans;
    }
}
